package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript: 旋转数组的最小数字，非递减序列，就是说要么递增，要么相等 {1,2,3,3,3,3,3,3,3}
 * 旋转后 {3,3,3,3,1,2,3,3,3,}
 * Question 7
 * @date: 2021/3/8 20:05
 * @version: 1.0
 */
public class Q7_MinNumberInRotateArray {
    public static void main(String[] args) {
        //int[] arr={3,3,3,3,1,2,3,3,3,4};
        //int[] arr={1,2,3,4,5};
        int[] arr={3,4,1,2,3};
        System.out.println(minNumberInRotateArray(arr));
    }

    public static int minNumberInRotateArray(int [] arr) {
        if (arr.length==0||arr==null){
            return 0;
        }
        if (arr.length==1){
            return arr[0];
        }

        int l=0,r=arr.length-1,mid;
        while(r > l ){
        //while(l<r){
            //r-l >= 2	->	mid > l
            mid = l + ((r - l) >> 1);
            if( arr[l + 1] >= arr[l] && arr[mid] >= arr[l]){
                r = mid;
            }else{
                l = mid;
            }
        }
        return arr[l];
    }
}
